#include<iostream>
#include<vector>
#include<stack>
#include<string>
#include<queue>
#include<algorithm>
#include<unordered_set>
using namespace std;



class Solution{//有向无环图
    private:
    vector<vector<int>>edges;
    vector<int> visited;
    bool valid = true;

    public:
    //dfs
    void dfs(int u){
        visited[u] = 1;
        for(int v: edges[u]){
            if(visited[v] == 0){
                dfs(v);
                if(!valid){
                    return;
                }
            }else if(visited[v] == 1){
                valid = false;
                return;
            }
        }
    }

    bool ans1(int numCourses, vector<vector<int>>& prerequisites){
        edges.clear();
        visited.clear();
        edges.resize(numCourses);
        visited.resize(numCourses);
        for(auto& info: prerequisites){
            edges[info[1]].push_back(info[0]);
        }
        for(int i = 0; i != numCourses && valid; i++){
            if(!visited[i]){
                dfs(i);
            }
        }
        return valid;
    }

    //bfs
    bool ans2(int numCourses, vector<vector<int>>& prerequisites){
        edges.clear();
        visited.clear();
        edges.resize(numCourses);
        visited.resize(numCourses);
        for(auto& info: prerequisites){
            edges[info[1]].push_back(info[0]);
            visited[info[0]]++;
        }

        queue<int> q;
        for(int i = 0; i != numCourses; i++){
            if(visited[i] == 0){
                q.push(i);
            }
        }

        int temp = 0;
        while(!q.empty()){
            temp++;
            int u = q.front();
            q.pop();
            for(int v: edges[u]){
                visited[v]--;
                if(visited[v] == 0){
                    q.push(v);
                }
            }
        }
        return temp == numCourses;
    }

    
};



void test1(){
    vector<vector<int>> pre = {
        {1,0}
    };
    int numCourse = 2;

    Solution s;
    // bool ret = s.ans1(numCourse, pre);
    bool ret = s.ans2(numCourse, pre);
    cout << ret << endl;
    
}

void test2(){
    vector<vector<int>> pre = {
        {1,0},
        {0,1}
    };
    int numCourse = 2;

    Solution s;
    // bool ret = s.ans1(numCourse, pre);
    bool ret = s.ans2(numCourse, pre);
    cout << ret << endl;
    
}

void test3(){
    vector<vector<int>> pre = {
        {1,2},
        {2,3},
        {1,4},
        {3,4}
    };
    int numCourse = 5;

    Solution s;
    // bool ret = s.ans1(numCourse, pre);
    bool ret = s.ans2(numCourse, pre);
    cout << ret << endl;
    
}


int main(void){
    test1();
    cout << "-----------------------------" << endl;
    test2();
    cout << "-----------------------------" << endl;
    test3();

    return 0;
}